Title:
Une perspective sur la résolution de trois problèmes
d'optimisation combinatoire.


Author:
Daniel Porumbel
(LGI2A, Université d'Artois)

Abstract:
The first part of this talk is devoted to a brief overview of several
research projects carried out on three problems:
a) graph coloring
b) graph isomorphism and graph matching
c) the computation of the distance between partitions

After a few details on isomorphism testing, the second part of the
talk is focused on local search heuristics for graph coloring. We present
two "distance-guided" algorithms that work on top of a local
search process. We use search space distance information
so as to control the trajectory of the underlying local search (i.e. Tabu
Search).

The first algorithm performs a coarse-grained recording of its own
trajectory by recording a limited number of spheres (a sphere is the
set of potential solutions situated within a distance R from its
center). A second intensification algorithm performs deep investigations only
within a "limited perimeter" of the search space, in the proximity of
 a given potential solution. For this, it employs a breath-first-search
routine to enumerate all R-spheres from this "limited perimeter". We
experimentally observed that if such a "limited perimeter" contains a
global optimum, the intensification algorithm does not fail in
eventually finding it.